Preuve de la fidélité du système RSA - Corrigé

Énoncé

Soit \(p\) et \(q\) deux nombres premiers distincts. On note \(N=pq\) et \(n=(p-1)(q-1)\) . 
Soit \(c\) un entier tel que \(1 \leqslant c et \(\mathrm{PGCD}(c;n)=1\) .

1. Soit \(a\) un entier naturel premier avec \(p\) et \(q\) .
    a. Démontrer que \(a^{n} \equiv 1 \ [p]\) et \(a^{n} \equiv 1 \ [q]\) .
    b. En déduire que \(a^{n} \equiv 1 \ [N]\) .

2. Démontrer que, pour tout \(a \in \mathbb{N}\) , si \(k\) est un entier qui vérifie \(k \equiv 1 \ [n]\) , alors \(a^k \equiv a \ [N]\) .

3. a. Justifier que l'équation \((E) \colon cx-ny=1\) admet des solutions dans \(\mathbb{Z}^2\) .
    b. Soit \((x_0;y_0)\) une solution particulière de \((E)\) . Prouver que \((x;y)\) est solution de \((E)\) si, et seulement si, \(x=x_0+kn\) et \(y=y_0+kc\) où \(k \in \mathbb{Z}\) .
    c. En déduire qu'il existe un unique entier \(d\) tel que \(1 \leqslant d et \(cd \equiv 1 \ [n]\) .

4. En utilisant les questions précédentes, montrer que pour tout  \(a\) , \(b \in \mathbb{N}\) , si \(b \equiv a^c \ [N]\) , alors \(b^d \equiv a \ [N]\) .

Solution

1. a. Comme \(a\) et \(p\) sont premiers entre eux, le nombre premier \(p\) ne divise pas \(a\) .
D'après le petit théorème de Fermat (forme forte), on a donc : \(a^{p-1} \equiv 1 \ [p]\) .
En élevant à la puissance \((q-1)\) , on a donc :  \(a^{(p-1)(q-1)} \equiv 1^{q-1} \equiv 1 \ [p]\) , 
autrement dit :   \(a^n \equiv 1 \ [p]\) .
De manière analogue, en échangeant les rôles de \(p\) et \(q\) , on prouve que \(a^n \equiv 1 \ [q]\) .

    b. D'après la question 1.a, \(a^n-1\) est divisible par \(p\) et par \(q\) .
Comme \(p\) et \(q\) sont deux nombres premiers distincts, ils sont premiers entre eux.
D'après le corollaire du théorème de Gauss, on en déduit que \(a^n-1\) est divisible par \(pq=N\) , c'est-à-dire que \(a^n \equiv 1 \ [N]\) .

2. Soit \(a \in \mathbb{N}\) . Soit \(k \in \mathbb{Z}\) tel que \(k \equiv 1 \ [n]\) .
Il existe un entier \(m \in \mathbb{Z}\) tel que \(k=1+nm\) , et donc 
\(\begin{align*}a^k\equiv a^{1+nm}\equiv a \times (a^n)^m\equiv a \times 1^m\equiv a \times 1\equiv a \ [N]\end{align*}\)  
donc \(a^k \equiv a \ [N]\) .

3. a. Comme \(\mathrm{PGCD}(c;n)=1\) et comme \(1\) divise \(1\) , l'équation diophantienne \((E)\) admet des solutions dans \(\mathbb{Z}^2\) .

    b. Soit \((x_0;y_0)\) une solution de \((E)\) .
On a alors :  \(\begin{align*} cx-ny=cx_0-ny_0 & \ \ \Longleftrightarrow \ \ c(x-x_0)=n(y-y_0)\end{align*}\)  
donc \(c\) divise \(n(y-y_0)\) .
Or \(\mathrm{PGCD}(c;n)=1\) , donc, d'après le théorème de Gauss, \(c\) divise \(y-y_0\) ,
c'est-à-dire qu'il existe \(k \in \mathbb{Z}\) tel que  \(y-y_0=kc\) , c'est-à-dire  \(y=y_0+kc\) .
On a alors
\(\begin{align*}c(x-x_0)=n(y-y_0)& \ \ \Longleftrightarrow \ \ c(x-x_0)=n \times kc\\& \ \ \Longleftrightarrow \ \ x-x_0=kn\\& \ \ \Longleftrightarrow \ \ x=x_0+kn\end{align*}\)  
et ainsi, on a bien \((x;y)=(x_0+kn;y_0+kc)\) avec \(k \in \mathbb{Z}\) .

Réciproquement, soit \(k \in \mathbb{Z}\) quelconque et \((x;y)=(x_0+kn;y_0+kc)\) . 
On a :  \(cx-ny=c(x_0+kn)-n(y_0+kc)=cx_0+kcn-ny_0-kcn=cx_0-ny_0=1\)  
car \((x_0;y_0)\) est une solution particulière de \((E)\) . Ainsi, \((x;y)\) est solution de \((E)\) .

     c. Soit \((x;y)\) une solution de \((E)\) . On a alors \(cx-ny=1\) et donc \(cx \equiv 1 \ [n]\) .
D'après la question 3.b, il existe \(k \in \mathbb{Z}\) tel que \(x=x_0+kn\) et \(y=y_0+kc\) où \((x_0;y_0)\) est une solution particulière de \((E)\) . On a alors :
\(\begin{align*}0 \leqslant x 
et comme \(k\) est entier, il n'existe qu'un seul entier \(k_0\) vérifiant l'encadrement ci-dessus.
En notant \(d=x_0+k_0n\) , on a donc \(cd \equiv 1 \ [n]\) et \(1 \leqslant d (il est clair que \(d \neq 0\) , sinon on aurait une contradiction dans la congruence précédente), et l'entier \(d\) vérifiant ces conditions est unique par unicité de l'entier \(k_0\) .

4. Soit \(a\) , \(b \in \mathbb{N}\) . On suppose que \(b \equiv a^c \ [N]\) .
On a alors :  \(b^d \equiv (a^c)^d \equiv a^{cd} \ [N]\) .
D'après la question 3.c, on a \(cd \equiv 1 \ [n]\) ; donc d'après la question 2, on en déduit que \(a^{cd} \equiv a \ [N]\) .
Par transitivité, on a donc :  \(b^d \equiv a^{cd} \equiv a \ [N]\) .